package com.pandy.code;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 异或运算高级题目
 * 配合对数器
 *
 * 一个数组中有一种数出现K次，其他数都出现M次
 * M > 1,K < M,找到出现K次的数
 *
 * 要求：额外空间复杂度O(1)，时间复杂度O(N)
 */
public class Code03_XOR_KM {

    /**
     * 对数器方法
     * @param arr
     * @param k
     * @param m
     * @return
     */
    public static int getKValue(int[] arr,int k, int m) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<arr.length; i++) {
            if(map.get(arr[i]) != null) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }

        for(Integer key : map.keySet()) {
            if(map.get(key) == k) {
                return key;
            }
        }
        throw new RuntimeException("数据不存在");
    }

    /**
     * 算法
     * @param arr
     * @param k
     * @param m
     * @return
     */
    public static int getKValue1(int[] arr,int k, int m) {

        return 0;
    }

    /**
     *
     * @param valueKinds 数组中数据的种类数
     * @param maxValue
     * @param k
     * @param m
     * @return
     */
    public static int[] createArray(int valueKinds,int maxValue,int k, int m) {
        int length = k + (valueKinds-1) * m;
        int[] arr = new int[length];

        // 生成数 -- 一种数出现K次
        int kValue = getRandomNum(maxValue);
        int index = 0;
        for(; index<k; index++) {
            arr[index] = kValue;
        }
        valueKinds -= 1;

        // 生成其他数 -- 其他数都出现M次
        Set<Integer> set = new HashSet<>();
        set.add(kValue);
        while (valueKinds > 0) {
            int mValue = 0;
            do{
                mValue = getRandomNum(maxValue);
            }while (set.contains(mValue));
            valueKinds--;
            for(int i=0;i<m;i++) {
                arr[index++] = mValue;
            }
        }

        // 打乱数组顺序
        for(int i=0;i<length;i++) {
            int a = (int)(Math.random() * length);
            int b = (int)(Math.random() * length);
            swap(arr,a,b);
        }


        return arr;
    }

    public static int getRandomNum(int maxValue) {
        return (int)(Math.random() * maxValue) - (int)(Math.random() * maxValue);
    }

    public static void swap(int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void print(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxValue = 100000;
        int testTime = 5;

        int valueKinds = 5;
        int k = 3;
        int m = 5;


        for(int i=0; i<testTime; i++) {
            int[] arr = createArray(valueKinds, maxValue, k, m);
            print(arr);
            System.out.println(getKValue(arr,k,m));
        }
    }
}
